#include <stdio.h>
// 堆栈
/*
计算机如何进行表达式求值？
表达式由运算数和运算符号组成，不同的运算符号优先级不一样
后缀表达式，从左到右依次入栈，后入栈的在上面，先入栈的在下面
当是数字的时候直接进栈，当是运算符号的时候，就将栈最上面两个数拿出进行计算后再将结果进栈。（栈顶元素永远在运算符号的右边）


-->启示：需要有一种存储方法，能顺序存储运算数，并在需要时倒序输出

叠盘子？
堆栈：只在一端（栈顶，Top）做插入，删除
插入数据：入栈（Push）
删除数据：出栈（Pop）
后入先出：Last In First Out(LIFO)
*/

// 用一个一维数组和一个记录栈顶元素位置的变量来表示栈
#define MAXSIZE 10
typedef struct SNode *Stack;
struct SNode
{
    int Data[MAXSIZE];
    int Top;
};

// （1）入栈
void Push(Stack PtrS, int item)
{
    if (PtrS->Top == MAXSIZE - 1)
    {
        printf("栈满");
        return;
    }
    else
    {
        PtrS->Data[++PtrS->Top] = item;
        return;
    }
}

//(2)出栈
int Pop(Stack PtrS)
{
    if (PtrS->Top == -1)
    {
        printf("栈空");
        return -1;
    }
    else
    {
        return PtrS->Data[(PtrS->Top)--];
    }
}

// 请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间，入栈操作就可以成功
/*
分析：如果简单地把数组分为两块，每一块都从左往右入栈，那么必然会造成空间浪费
我们不妨换个思路，一个从左往右入栈，另一个从右往左入栈，这样是不是就能解决问题了呢？
*/
struct DStack
{
    int Data[MAXSIZE];
    int top1;
    int top2;
} S = {
    .top1 = -1,
    .top2 = MAXSIZE};

void DoubleStack_Push(struct DStack* PtrS,int item,int Tag)
{
    //用Tag区分放入哪个堆栈，值为1或2
    if(PtrS->top2 - PtrS->top1 == 1)
    {
        printf("栈满");
        return;
    }
    if(Tag == 1)
    {
        PtrS->Data[++PtrS->top1] = item;
        return;
    }
    else
    {
        PtrS->Data[--PtrS->top2] = item;
        return;
    }
}

int DoubleStack_Pop(struct DStack* PtrS,int Tag)
{
    if(Tag == 1)
    {
        if(PtrS->top1 == -1)
        {
            printf("栈空");
            return -1;
        }
        else
            return PtrS->Data[PtrS->top1--];
    }
    else
    {
        if(PtrS->top2 == MAXSIZE)
        {
            printf("栈空");
            return -1;
        }
        else
            return PtrS->Data[PtrS->top2++];
    }
}




